#Exercise 1.11.  A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - #2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a #procedure that computes f by means of a recursive process.

#python:
calls = 0
def f(n):
    global calls
    calls += 1
    return n if n < 3 else (f(n - 1) + 2 * f(n-2) + 3 * f(n-3)  )

calls = 0
f(26)
# 1930252097
calls
# 4966849


##Para n ~25 temos milhoes de chamadas
## o que nos leva a !! um decorator para cachear o resultado!

from functools import wraps
from cPickle import dumps

def cached(func):
    cached_results = {}
    @wraps(func)
    def cacher_func(*args, **kw):
        index = dumps((args, kw))
        if index in cached_results:
            return cached_results[index]
        results = func(*args, **kw)
        cached_results[index] = results
        return results
    return cacher_func

@cached
def fc(n):
    global calls
    calls += 1
    return n if n < 3 else (fc(n - 1) + 2 * fc(n - 2) + 3 * fc(n - 3)  )

calls = 0
fc(26)
# 1930252097
calls
27

## Reduzido para n + 1 chamadas, mesmo para numeros grandes,
## para cada cálculo, sem ser necessário
## uma anpálise matemática e  re-escrita do algoritmo!
##

#procedure that computes f by means of an interactive process.
#not working
def fi(n):
    if n < 3: return n
    vals = [0, 1, 2]
    i = 3
    result = 0
    while i <= n:
        result += vals[(i - 1) % 3] + 2 * vals[(i - 2) % 3] + 3 * vals[(i - 3) % 3]
        vals[i % 3] = result
        i += 1
    return result
